This application claims priority under 35 U.S.C. xc2xa7xc2xa7119 and/or 365 to 9804076-9 filed in Sweden on Nov. 26, 1998; the entire content of which is hereby incorporated by reference.
1. Field of Invention
The present invention relates to a method of regulating load in a distributed database.
In a distributed database, information entering the database is distributed between several different database nodes. A request from a user is served either by the node to which the user connects, which is here called a receiving node, or by another of said nodes that is able to meet the request, after the receiving node having forwarded the request to said other node. A node that can meet the request is here called the serving node.
2. Description of the Background Art
It has long been known that in the case of a distributed database in which information or data belonging to the database is distributed between several different nodes a user need not necessarily know in which node the requested information is found, but simply connects to a node and asks to be allowed to perform an operation in the database.
This operation may be one in which the user requires access to information in the database, or access to one or more objects therein, for instance to read the object or to write into the object.
The receiving node may itself be a serving node that can meet the request, or forwards the request to the node in the database that can deal with the request, in other words the node that includes the requested object.
It should be mentioned that there is a difference between an operation and a transaction. A transaction includes a plurality of operations, where the number of operations concerned will depend on the complexity of the transaction.
It is also known that the total executing capacity of a database is equal to the sum of the executing capacities of all the nodes in the database. When requests are made to the various nodes and these requests need to be distributed between said nodes, hot spots are liable to occur which overload one node whilst leaving other nodes spare capacity, despite the fact that the total capacity of the database has not been used to the full.
Several different methods of solving this problem are known to the art, these methods normally being referred to as load regulating methods.
Prior Publication U.S. Pat. No. 5,450,584 teaches a load regulating method where an internal load monitoring unit in each node monitors the extent to which the own node is loaded, and an external load monitoring unit in each node that monitors the extent to which each other node is loaded. A central unit for handling the load distribution within the database is connected to each unit for load monitoring purposes.
The central load distributing unit functions to shift information from a node which, via its internal load monitoring unit, indicates that the internal node has exceeded a highest permitted level, to a selected other node in the database. This movement of information, often requested information, from a heavily loaded node to a less loaded node results in more uniform distribution of the load between the nodes in the database.
Prior Publication EP-A2-0 642 092 teaches a method of regulating the load within a parallel database system. Load distribution is governed by the way the information in the database can be redistributed from an active node to a new node or to an unused node.
This method is thus also based on the redistribution of information in the database between the nodes included therein.
Prior Publications U.S. Pat. Nos. 5,551,027, 5,379,424, 5,668,986 and 5,606,693 describe further methods for regulating the load in distributed databases or distributed information within a computer system.
Technical Problems
When considering the present state of the art as described above, it will be seen that a technical problem resides in enabling the load between the nodes of a distributed database to be regulated in the absence of a central function that monitors the load on the nodes in said database or which handles the total load regulation therein.
A further technical problem is one of providing a load regulating facility that requires no co-ordination between the database nodes, but which can be implemented and handled locally in respective nodes.
A further technical problem is one of providing a load regulating facility that regulates the load between the nodes in the database without needing to re-distribute the information content of said database between the different nodes to this end.
Another technical problem is one of regulating incoming requests to each node in a manner that will ensure that the total number of requests to the database will not exceed its total execution capacity.
Yet another technical problem is one of enabling such limitation to be related to the number of requests that are allowed to enter the database via each individual node.
A further technical problem is one of providing requests with a waiting option when load regulation has shown that a request cannot be permitted because of the danger of overloading the database.
In this respect, a technical problem is one of limiting the request waiting time, and therewith the database response time, when a request cannot be allowed because of the danger of overloading the database.
Another technical problem is one of ensuring that no hot spots will occur in the database, and that this assurance can be upheld in a database that includes nodes of different executing capacities.
When a transaction requested by a user can be divided into a number of operations, and when each commanded operation is comprised of a request, a technical problem resides in ensuring that requests belonging to a transaction that has already commenced can be met so that ongoing transactions can be completed and need not be discontinued or aborted.
Another technical problem is one of enabling a database to be load-regulated with a starting point from the number of incoming requests, where each request comprises a command operation.
A further technical problem is one of enabling the load on a database to be regulated with a starting point from the execution cost incurred by respective requests.
Still another technical problem is one of allotting a relevant execution cost to respective requests.
When no more requests can be permitted through a specific receiving node and when other nodes are able to permit more requests to be undertaken in their capacity as receiving nodes, a technical problem resides in still enabling the specific receiving node to receive more requests.
Another technical problem is one of handling a request that comprises an operation which can be divided into several parts, such as a review of the entire database or a review of parts thereof, when the receiving node and/or one or more other nodes do have the capacity to meet the request.
It is then also a technical problem to handle a request that comprises an operation which can be divided into several parts, such as a review of the entire database or a review of parts thereof, when the receiving node and/or one or more other nodes do not have the capacity to meet the request.
Solution
With the intention of solving one or more of the aforesaid technical problems, the present invention takes as its starting point a distributed database where information within the database is distributed between several different nodes belonging to said database, wherein a user request is served either by the node to which the user connects, here referred to as a receiving node, or by some other node after the receiving node has forwarded the request to one of those nodes capable of meeting the request, these nodes being referred to as serving nodes.
With the intention of providing a method of regulating the load in such a database in which no central controlling or monitoring facility is used with respective nodes, it is proposed in accordance with the invention that respective nodes are allocated one or more key-numbers which function to limit the number of requests that respective nodes may accept in their role as a receiving node, and that these key-numbers are related to the executing capacity of the database.
With the intention of limiting the number of requests that can be permitted and therewith ensure that the total execution capacity of the database will not be exceeded, it is proposed in accordance with the invention that respective nodes are allocated a first key-number, and that this first key-number relates to a highest permitted number of requests that can be made to the database via a current receiving node.
It is also proposed in accordance with the invention that used parts of the first key-number are designated used first key-number parts, while unused parts of the first key-number are designated unused first key-number parts.
With the intention of providing a waiting option with respect to requests when the first key-number of the receiving node shows that the request cannot be met, and with the intention of limiting any waiting times and therewith obtain acceptable database response times, it is proposed in accordance with the invention that respective nodes are allocated a first queue belonging to said first key-number, and that said first queue is related to a highest permitted number of requests that can be placed in the queue, or line, so as not to exceed the first key-number.
It is also proposed in accordance with the present invention that used parts of the first queue are designated used first queue places, where empty or unused parts of said first queue are designated unused first queue places.
A user requested transaction can be divided into one or more operations. It is then possible for each commanded operation to constitute a request.
With the intention of giving those transactions that have already been commenced priority over transactions that have not yet been started, it is proposed in accordance with the invention that respective nodes are allocated a second queue, or line, belonging to the first key-number. In the two queues associated with the first key-number, the first queue is related to the highest permitted number of requests belonging to a commenced transaction that can be placed in line in the queue.
Those transactions that have not yet been commenced are placed in the second queue, or line, this queue relating to the highest permitted number of requests belonging to non-commenced transactions that can be placed in line.
Requests in the second queue may not have access to the database until the first queue is empty, in other words all requests in the first queue have access to the database before dealing with requests in the second queue.
The first key-number and its two queues ensure that the total execution capacity of the database will not be exceeded.
With the intention of avoiding hot spots in the database, it is proposed in accordance with the invention that respective nodes are allocated a second key-number, and that this second key-number is related to the highest permitted number of requests that may be forwarded to one and the same serving node in the database. Used parts of the second key-number are designated used second key-number parts, and unused parts of said second key-number are designated unused second key-number parts.
When the database nodes have mutually different execution capacities, it is proposed in accordance with the invention that the nodes can be divided into node groups, each in accordance with the execution capacity of respective nodes, where nodes belonging to a first group have a first execution capacity, where nodes belonging to a second group have a second execution capacity, and so on. When the nodes are so divided, respective nodes are allocated a first second key-number related to the execution capacity of the nodes belonging to the first group, and respective nodes are allocated a second second key-number related to the execution capacity of the nodes belonging to said second group, and so on.
It is also proposed in accordance with the present invention that respective nodes are allocated a third key-number and that the third key-number relates to a highest number of transactions permitted to enter the database via respective receiving nodes. Used parts of the third key-number are designated used third key-number parts, and unused parts of the third key-number are designated unused third key-number parts.
The third key-number functions to ensure that only a given number of transactions can make requests simultaneously to one and the same receiving node. Thus, the first key-number with its first queue, or line, together with the third queue number gives priority to ongoing transactions over new not yet commenced transactions.
The third key-number can be set so that the number of transactions entering the database via one and the same node will be lower than would be possible according to the first key-number and its two queues.
It is also possible to include an hysteresis in the use of the third key-number, i.e. the third key-number can be made to stop the number of transactions at a first value and allows further transactions at a second value where the first value is greater than the second value.
According to the aforegoing, the different key-numbers are related to incoming requests. When a user command transaction can be divided into more than one operations, and when each commanded operation is comprised of a request, it is proposed in accordance with the present invention that respective key-numbers and queues are determined in permitted number of operations, that is with the exception of the third key-number which is determined in the permitted number of transactions. This enables the load on the database to be regulated in accordance with the number of operations commanded by to incoming requests.
According to the present invention, it is also possible to allocate a so-called execution cost to respective operations, and to determine respective key-numbers and queues, with the exception of the third key-number, in the permitted execution cost. This enables the load on the database to be regulated, or controlled, in accordance with the execution cost incurred by the operations in conjunction with incoming requests.
Such execution costs can be determined in several ways. According to one inventive method, the execution cost is determined with respect to the number of bytes included in the command string associated with the operation.
According to another inventive method, the execution cost of an operation is determined by dividing the operations into different types of operation, such as the insertion of data, reading of data, updating data or deleting data, and the execution cost is determined with respect to the type of operation concerned and with respect to the amount of data, or information, concerned in the operation.
With the intention of allowing the receiving node to receive more requests despite the fact that said node is unable to receive more requests without exceeding the first key-number and its associated queues, it is proposed in accordance with the present invention that the receiving node is allowed to borrow unused first key-number parts, unused first queue places and/or unused second queue places from some other node that has unused first key-number parts and/or unused queue places, therewith allowing an extra number of requests to be made to the database in addition to the first key-number and its queue places for the receiving node, this additional number of requests corresponding to the number of unused first key-number parts, empty queue places and/or second queue places belonging to the second node. A number of the unused first key-number parts, the first queue places and/or the second queue places belonging to the second node corresponding to said additional number of permitted requests are then considered to be used queue places.
A request may also constitute a so-called large operation that can be divided into several parts, such as a review of the entire database or of parts thereof. In the case of a request of this nature, it is proposed in accordance with the present invention that the operation is carried out as a single operation when the number of unused first key-number parts, the number of first queue places and/or the number of second queue places of the receiving node and/or one or more other nodes is sufficient to this end.
If, on the other hand, the number of unused first key-number parts, the number of first queue places and/or the number of second queue places of the receiving node and other nodes is insufficient to carry out the operation, it is proposed in accordance with the present invention that the operation is allocated one or more first key-number parts and second key-number parts and also a third key-number part. While the operation uses the third key-number part, a first part of the operation is carried out by using the first and the second key-number parts, whereafter a second part of the operation is also performed by using the first and the second key-number parts, and so on, until all parts of the operation have been carried out, whereafter the first, second and third key-number parts are again available for other operations.
In conjunction with operations of this kind that can be divided into several smaller parts, it is proposed in accordance with the invention that respective nodes are allocated a fourth key-number, and that the fourth key-number is related to a highest permitted number of parts of relevant key-numbers that can be allocated to so-called large operations.
This prevents large operations from seizing the entire capacity of a receiving node, or nodes, because part of the key-numbers concerned remain to serve requests other than those associated with the large operation or operations.
According to the present invention, the fourth key-number shall be smaller than or equal to the first key-number.
Advantages
The advantages primarily characteristic of an inventive method reside in the ability to regulate, or control, the load on the nodes in a database without needing to use a central monitoring and regulating function to this end. The load is controlled by using in each individual node key-numbers that may not be exceeded. The inventive method thus requires no active control or no redistribution of the data content of the database between the nodes therein.
The method also enables hot spots to be avoided in the database. Another advantage is that when a receiving node is unable to receive more requests because it has no unused parts and/or no empty queue places in the own node, parts and/or queue places can be xe2x80x9cborrowedxe2x80x9d from nodes that are not equally as loaded at that point in time.
The main characteristic features of an inventive method are set forth in the characterising clause of the following claim 1.